#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
void Print(int* p, int n)
{
	for (int i = 0; i < n; i++) {
		printf("%d ", p[i]);
	}
	printf("\n");
}
void ShellSort(int* p, int n)
{
	int gap = 3;
	for (int i = 0; i < gap; i++) {
		for (int j = i; j < n - gap; j += gap) {
			int end = j;
			int tmp = p[end + gap];
			while (end >= gap) {
				if (p[end] >= tmp) {
					p[end + gap] = p[end];
				}
				else {
					break;
				}
				end -= gap;
			}
			p[end + gap] = tmp;
		}
	}
	for (int i = 0; i < n - 1; i++) {
		int end = i;
		int tmp = p[end + 1];
		while (end >= 0)
		{
			if (p[end] >= tmp) {
				p[end + 1] = p[end];
			}
			else {
				break;
			}
			end--;
		}
		p[end + 1] = tmp;
	}
}
void test()
{
	int arr[] = { 3,4,2,1,-4,-9,0,9,6,8,7,5 };
	int n = sizeof(arr) / sizeof(int);
	ShellSort(arr, n);
	Print(arr, n);

}
int main()
{
	test();

	return 0;
}